1. Field of the Invention
The present invention is related to a data transfer system using iterative signal processing to decode convolutionally coded signals, and more particularly, to a turbo decoder by implementing the iterative decoding and a method to generate a stopping signal to stop the iterative decoding.
2. Description of the Prior Art
Turbo code is a capacity-approaching error correction code having high performance. Because of its high performance and proper decoding complexity, it has been widely used in many communication systems, such as CCSDS standard in deep space, DVB-RCS standard in broadcast systems, W-CDMA, WiMAX or 3GPP-LTE in cellular systems, etc.
The turbo decoding principle is further extended to other iterative signal processing such as serial turbo codes, hybrid turbo codes, turbo equalization, turbo detection, etc.
The turbo code disclosed in U.S. Pat. No. 5,446,747 is constructed by parallel concatenating two convolutional codes via an interleaver. Similar to '747, the conventional turbo decoder adopts iterative way to decode. The decoder is a decoding loop, which connects a first maximum a-posteriori (MAP) decoding module, an interleaver, a second MAP decoding module, and a deinterleaver in series. In that, the main function of MAP decoding module is to calculate a-posteriori probability (APP) and is usually implemented by the BCJR algorithm. The BCJR algorithm was published by Bahl et al. in IEEE Transactions on Information Theory in March 1974. Moreover, the prior art '747 disclosed that after receiving a data block, the data enters the decoding loop via the first MAP decoder. Then, one iteration of decoding is performed by the first MAP decoding, interleaving, the second MAP decoding and deinterleaving in order. The conventional turbo decoding performs iterative decoding using a fixed number of iterations. The more the number of iterations is performed, the higher the accuracy of data is obtained. The performance can be close to Shannon's channel capacity limit. However, when the number of iterations is increased, the performance improvement is reduced gradually and saturated accordingly. More iterations will only increase the power consumption and decoding delay, therefore it is necessary to have a stopping method to solve this problem.
When the turbo decoding is implemented in handheld or portable devices, power consumption is a very important issue. How to design a proper stopping method for iterative decoding is an issue to be resolved. By reviewing some presently known prior art, the stopping methods published by Wang et al. in IEEE ICASSP'06 in May 2006 were categorized into two classes. One class is based on soft information such as cross entropy (CE), sign change ratio (SCR), and sign difference ratio (SDR). The other is based on hard-decision information such as hard decision aided (HDA). The aforementioned prior art are good in saving the number of iterations for iterative decoding, but they suffer from shortcomings of requiring large memory and complicated calculations.
The operation related to the CE method published by Hagenauer et al. in IEEE Transactions on Information Theory in March 1996 is briefed in the following. Please refer to FIG. 1, it is a block diagram illustrating a turbo decoder with CE stopping method. The turbo decoder consists of a conventional turbo decoding module 10′ and a stopping method module 20′. The turbo decoding module 10′ basically is a decoding loop and comprises a first MAP decoding module (MAP1) 101′, an interleaver (π) 103′, a second MAP decoding module (MAP2) 102′ and a deinterleaver (π−1) 104′. The turbo decoding module 10′ is configured to receive convolutionally coded signals and perform iterative decoding. When finishing one iteration, the a-priori information and/or extrinsic information is generated and transferred to the stopping method module 20′. The stopping method module 20′ proceeds to calculate the cross-entropy at 201′ and determine the stopping condition at 202′. It then outputs a stopping signal 203′ to the turbo decoding module 10′ so as to control whether to continue iterative decoding or not.
Still refer to the MAP decoding module in FIG. 1, the MAP decoding module is typically performed the logarithmic BCJR algorithm, which is easier to be implemented and also named as Log-MAP algorithm. The algorithm was published by Robertson in IEEE ICC'95 in June 1995. It is summarized as follows, where some of the superscripts and subscripts are omitted for convenience.
                              γ          ~                k            ⁡              (                              s            ′                    ,          s                )              =                            1          2                ⁢                              u            k                    ⁡                      (                                          L                a                            +                              L                s                                      )                              +                        1          2                ⁢                  L          p                ⁢                  x          k          p                      ,          ⁢                              α          ~                k            ⁡              (        s        )              =                                        max            *                                              s              ′                        ∈                          S                              k                -                1                                                    ⁢                  {                                                                      α                  ~                                                  k                  -                  1                                            ⁡                              (                                  s                  ′                                )                                      +                                                            γ                  ~                                                  k                  -                  1                                            ⁡                              (                                                      s                    ′                                    ,                  s                                )                                              }                    -              H        k              ,          ⁢                              β          ~                k            ⁡              (                  s          ′                )              =                                        max            *                                              s              ′                        ∈                          S                              k                +                1                                                    ⁢                  {                                                                      β                  ~                                                  k                  +                  1                                            ⁡                              (                s                )                                      +                                                            γ                  ~                                k                            ⁡                              (                                                      s                    ′                                    ,                  s                                )                                              }                    -              G        k              ,          ⁢            L      d        =                                        max            *                                              (                                                s                  ′                                ,                s                            )                        ∈                          E              +                                      ⁢                  {                                                                      α                  ~                                k                            ⁡                              (                                  s                  ′                                )                                      +                                                            γ                  ~                                k                            ⁡                              (                                                      s                    ′                                    ,                  s                                )                                      +                                                            β                  ~                                                  k                  +                  1                                            ⁡                              (                s                )                                              }                    -                                    max            *                                              (                                                s                  ′                                ,                s                            )                        ∈                          E              -                                      ⁢                  {                                                                      α                  ~                                k                            ⁡                              (                                  s                  ′                                )                                      +                                                            γ                  ~                                k                            ⁡                              (                                                      s                    ′                                    ,                  s                                )                                      +                                                            β                  ~                                                  k                  +                  1                                            ⁡                              (                s                )                                              }                      ,          ⁢            L      e        =                  L        d            -              L        s            -              L        a              ,where the subscript k is the kth time instant; {tilde over (γ)}k(s′,s) is the branch metric from state s′ to state s; ukε{+1, −1} is the value of transmitted symbol; E+/E− is the set of (s′,s) branch pair corresponding to uk=+1/uk=−1, respectively; {tilde over (α)}k (s) is the forward state metric; {tilde over (β)}k (s′) is the backward state metric; Ld/La/Le are the APP/a-priori information/extrinsic information, respectively; Lc is the channel reliability, yks is the value of received systematic information symbol, LsLcyks is the log-likelihood ratio of yks; ykp is the value of received parity symbol, LpLcykp is the log-likelihood ratio of ykp; xkp, is the value of transmitted parity symbol; Hk and Gk are the normalized term for {tilde over (α)}k(s) and {tilde over (β)}k (s′), respectively; and max*{a,b}=max(a,b)+ln(1+e−|a-b|). Note that the dashed line in FIG. 1 such as Ld1 and Lp2 stands for the input or output signals of the turbo decoding module 10′ for convenience.
At the ith iteration, the stopping method module receives the ith APP (d1(i)=(Ld1,1(i), Ld1,2(i), . . . , Ld1,k(i), . . . , Ld1,N(i))), where N is data block length, of the first MAP decoding module and the ith extrinsic information (e2(i)=(Le2,1(i), Le2,2(i), . . . , Le2,N(i))) of the second MAP decoding module from the turbo decoding module and the cross-entropy is calculated as
            T      ⁡              (        i        )              ⁢          =      Δ        ⁢                  ∑                  k          =          1                N            ⁢                                                                              L                                                      e                    ⁢                                                                                  ⁢                    2                                    ,                  k                                                  (                  i                  )                                            -                              L                                                      e                    ⁢                                                                                  ⁢                    2                                    ,                  k                                                  (                                      i                    -                    1                                    )                                                                          2                          exp          ⁡                      (                                                        L                                                      d                    ⁢                                                                                  ⁢                    1                                    ,                  k                                                  (                  i                  )                                                                    )                                ,where the Le2,k(i-1) is the extrinsic information of the kth data bit of the second MAP decoding module at (i−1)th iteration and the exp (•) is exponential function. When the stopping condition is qualified as
                    T        ⁡                  (          i          )                            T        ⁡                  (          1          )                      <          ɛ      s        ,where εs is a threshold developed in accordance with bit error rate (BER) performance requirement, then a stopping signal 203′ is generated. The CE method is good in saving the number of iterations, but the drawbacks of requiring large memory (because the extrinsic information of entire data block e2(i-1)=(Le2,1(i-1), Le2,2(i-1), . . . , Le2,k(i-1), . . . , Le2,N(i-1)) is required to be memorized) and complicated calculations such as N exponential operations and N division operations are obvious.
The SCR method was published by Shao et al. in IEEE Transactions on Information Theory in August 1999. It is a simplified version of the CE method.
            T      ⁡              (        i        )              ≈                  δ        i            ·              C        ⁡                  (          i          )                      ,          ⁢            δ      i        =          E      ⁡              [                                                                                            L                                                            e                      ⁢                                                                                          ⁢                      2                                        ,                    k                                                        (                    i                    )                                                  -                                  L                                                            e                      ⁢                                                                                          ⁢                      2                                        ,                    k                                                        (                                          i                      -                      1                                        )                                                                                      2                                exp            ⁡                          (                                                                L                                                            d                      ⁢                                                                                          ⁢                      1                                        ,                    k                                                        (                    i                    )                                                                              )                                      ]              ,          ⁢            C      ⁡              (        i        )              =                  ∑                  k          =          1                N            ⁢              [                              sgn            ⁡                          (                              L                                                      e                    ⁢                                                                                  ⁢                    2                                    ,                  k                                                  (                  i                  )                                            )                                ⊕                      sgn            ⁡                          (                              L                                                      e                    ⁢                                                                                  ⁢                    2                                    ,                  k                                                  (                                      i                    -                    1                                    )                                            )                                      ]              ,where the E[•] is expectation function, the sgn(•) is sign function, the ⊕ is exclusive OR logic, and C(i) is the number of different signs of the extrinsic information between ith and (i−1)th iteration of the second MAP decoding module. When the stopping condition is qualified as
                    C        ⁡                  (          i          )                    N        <          ɛ      s        ,where εs is a threshold developed in accordance with BER performance requirement, then a stopping signal is generated. Because the SCR method is simplified, the saving of the number of iterations is not as good as CE. Similar to the CE method, the SCR method is also required more memories (because the signs of the extrinsic information of entire data block are required to be memorized).
For the HDA method, it is another Shao's method. The HDA method is a further simplified version of the CE method. When the stopping condition is qualified assgn(Le2,k(i))=sgn(Le2,k(i-1))for all k, then a stopping signal is generated. However, Shao et al. mentioned that the saving of iteration of the HDA method is not as good as the CE method or the SCR method in high SNR region. The HDA method is also required memories to store the signs of the extrinsic information of entire data block.
The SDR method was published by Wu et al. in IEEE Communications Letters in August 2000. It extends the idea of the SCR method to the a-priori information aj(i)=(Laj,1(i), Laj,2(i), . . . , Laj,k(i), . . . , Laj,N(i)) and the extrinsic information ej(i)=(Lej,1(i), Lej,2(i), . . . , Lej,k(i), . . . , Lej,N(i)) of a single MAP decoding module, where jε{1, 2} can be either the first MAP decoding module or the second MAP decoding module. When the stopping condition is qualified as
                              ∑                      k            =            1                    N                ⁢                  [                                    sgn              ⁡                              (                                  L                                      aj                    ,                    k                                                        (                    i                    )                                                  )                                      ⊕                          sgn              ⁡                              (                                  L                                      ej                    ,                    k                                                        (                    i                    )                                                  )                                              ]                    N        <          ɛ      s        ,where εs is a threshold developed in accordance with BER performance requirement, then a stopping signal is generated The SDR method does not required extra memories to store the signs of the extrinsic information of entire data block. Comparing the number of iteration saving, the SDR method is the worst.
More stopping methods were also discussed in the paper of Wang et al. The major difference is the signals transferred to the stopping method module being the a-priori information and/or extrinsic information. There are some pros and cons between the number of iteration saving and the BER performance. Due to the fact that an entire data block of the a-priori information and/or extrinsic information is needed to transfer to the stopping method module, a common drawback is high complexity of calculations for stopping condition (because at least N operations are required to calculate the stopping condition).
Generally, when the turbo decoding module is converged, the a-priori information aj(i), the extrinsic information ej(i) or the APP in the entire data block will be converged. Using an entire data block to design the stopping methods are the conventional methods in the prior art, such as U.S. Pat. Nos. 6,738,948, 6,898,254, 6,518,892, 6,956,912, and U.S. Patent App. US 2005/0015696, etc. The prior art are intuitive, but the drawback of requiring large memory and/or complicated calculations is obvious.